package leetcode

import kotlinetc.println

//https://leetcode.com/problems/subsets/
/**
Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
Accepted
374,450
Submissions
703,350
 */
fun main(args: Array<String>) {


    println(1 shl 3)

    subsets(intArrayOf(1,2,3)).println()

}


/**
 * 根据第几种，直接知道某一位是否被选中
 *
 * 0  ->  000
 * 1  ->  001
 * 2  ->  010
 * 3  ->  011
 * 4  ->  100
 */
fun subsets(nums: IntArray): List<List<Int>> {

    val possible = 1 shl nums.size
    val result = ArrayList<List<Int>>()

    for (i in 0 until possible) {
        val list = arrayListOf<Int>()
        for (j in 0 until nums.size) {
            if ((i shr j) and 1 == 1) {
                list.add(nums[j])
            }
        }
        result.add(list)
    }
    return result
}